package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:13
 * @Description:冒泡排序
 * 空间复杂度：O(1)
 * 最好时间复杂度：O(n)
 * 最坏时间复杂度：O(n*n)
 * 平均时间复杂度：O(n*n)
 * 是否受初始化数据影响：受,在数组完全有序情况下，O(n)
 * 思路：每次找出该层最大的值，让它“浮上去”
 * 循环：0起始的双层循环，第一层遍历数组中元素，第二层循环，不断比较，直到找出该层最大值
 */
public class BubbleSort {
    public static void bubbleSort(int[] arr,int n){
        int i,j;
        for(i=0;i<n;i++){
            boolean flag = false;
            for(j=0;j< n-i-1;j++){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if(!flag) break;
        }
    }

    private static void swap(int[] arr, int j, int i) {
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

    public static void main(String[] args) {
        int[] arr = {3,2,6,12,18};
        bubbleSort(arr,arr.length);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
